package com.wuxuan.algorithm_homework.dynamicPrograming;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * 动态规划
 */
public class DynamicProgramingDemo {
    /**
     * 1.零钱兑换
     *
     * 给你一个整数数组 coins ，表示不同面额的硬币;以及一个整数 amount ，表示总金额。
     * 计算并返回可以凑成总金额所需的 最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。
     * 你可以认为每种硬币的数量是无限的。
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount <= 0) {
            return 0;
        }

        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin && dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }


    @Test
    public void testCoinChange() {
        //示例 1:
        //输入:
        // coins=[1，2，5]，amount=11
        // 输出:3
        //解释:11=5+5+13
        System.out.println(new DynamicProgramingDemo().coinChange(new int[]{1, 2, 5}, 11));

        //示例 2:
        //输入:coins=[2]，amount=3输出:-1
        System.out.println(new DynamicProgramingDemo().coinChange(new int[]{2}, 3));
    }

    /**
     * 单序列问题
     * <p>
     *
     * 2. 打家劫舍
     * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
     * 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，
     * <p>
     * 计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        if (nums.length > 1) {
            dp[1] = Math.max(nums[0], nums[1]);
        }

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }


    @Test
    public void testRob() {
        //示例 1:
        //输入:[1,2,3,1]
        //输出:4
        //解释:偷窃1号房屋(金额=1)，然后偷窃3号房屋(金额=3)。
        //偷窃到的最高金额=1+3-4。
        System.out.println(new DynamicProgramingDemo().rob(new int[]{1, 2, 3, 1}));
        //示例 2:
        //输入:[2,7,9,3,1]
        //输出:12
        //解释:偷窃1号房屋(金额 = 2),偷窃3号房屋(金额 =9)，接着偷窃5号房屋(金额 = 1)。
        //偷窃到的最高金额=2+9+1=12。
        System.out.println(new DynamicProgramingDemo().rob(new int[]{2, 7, 9, 3, 1}));
    }


    /**
     * 路径规划问题
     * 不同路径 II
     *
     * 3.机器人行走路径数和
     *
     * 给定一个二维整数数组 grid ，一个机器人初始位于 grid[0][0]，
     * 需要移动到 grid[m-1][n-1]，机器人每次只能向下或者向右移动一步，且移动路径中不能包含障碍物。
     * 网格中存在的障碍物，用 1 表示，空位置用 0 表示，返回机器人能够到达目的的不同路径的数量，注意:移动路径中不能包含障碍物!
     *
     * @param obstacleGrid
     * @return
     */
    public int uniquePathWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
            return 0;
        }

        int[][] dp = new int[m][n];

        //初始化第一列
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                //一旦有障碍物，直接跳出循环！后面的遍历位置都不可能有路径
                break;
            }
            dp[i][0] = 1;
        }

        //初始化第一行
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 1) {
                break;
            }
            dp[0][j] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    //当前路径为上方路径和左方路径之和
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        //返回右下角的路径数
        return dp[m - 1][n - 1];
    }

    @Test
    public void testUniquePathWithObstacles() {
        //示例1:
        //输入:obstacleGrid=[[0, 1, 0],
        //                  [0, 0, 0],
        //                  [0，0，0]]
        //输出:
        // 3
        System.out.println(new DynamicProgramingDemo().uniquePathWithObstacles(new int[][]{{0, 1, 0}, {0, 0, 0}, {0, 0, 0}}));
    }

    /**
     * 4.编辑距离
     * <p>
     * 给定两个字符串 word1 和 word2，计算从字符串 word1 转换为 word2 所需的最少操作次数，允许的操作包括:
     * 插入一个字符。
     * 删除一个字符
     * 替换一个字符
     *
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        if (m * n == 0) {
            return m + n;
        }

        int[][] dp = new int[m + 1][n + 1];

        //初始化
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }

        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int deleteCost = dp[i - 1][j] + 1;
                int addCost = dp[i][j - 1] + 1;
                int replaceCost = dp[i - 1][j - 1] + (word1.charAt(i - 1) == word2.charAt(j - 1) ? 0 : 1);
                dp[i][j] = Math.min(Math.min(deleteCost, addCost), replaceCost);
            }
        }
        return dp[m][n];
    }

    @Test
    public void testMinDistance() {
        System.out.println(new DynamicProgramingDemo().minDistance("kitten", "sitting"));
    }
}
